746. 使用最小花费爬楼梯

https://leetcode-cn.com/problems/min-cost-climbing-stairs/solution/shi-yong-zui-xiao-hua-fei-pa-lou-ti-by-l-ncf8/

这题是很经典的递推 DP，算是真正的入门第一题了

创建长度为 $n+1$ 的数组 dp，其中 $dp[i]$ 表示达到下标 i 的最小花费。

由于可以选择下标 0 或 1 作为初始阶梯，因此有 $dp[0] = dp[1] = 0$。

当 $2 \le i \le n$ 时，可以从下标 i - 1 使用 $cost[i−1]$ 的花费达到下标 i，或者从下标 i-2 使用 $cost[i−2]$ 的花费达到下标 i。

为了使总花费最小，$dp[i]$ 应取上述两项的最小值，得出状态转移方程（递推公式）：

$dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])$

具体可以看这题的 题解

func minCostClimbingStairs(cost []int) int {
    n := len(cost)
    dp := make([]int, n + 1) // 因为需要更新最新一个数，所以 n + 1
    dp[0] = 0
    dp[1] = 0

    for i := 2; i <= n; i++ {
        dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
    }
    return dp[n]
}

func min(a, b int) int {
    if a > b {
        return b
    }

    return a
}

因为每次只是读取 dp 的前两个数，所以可以使用滚动的方式再一次优化

func minCostClimbingStairs(cost []int) int {
    n := len(cost)
    // dp[i]指针到达第i个阶梯时需要花费的最小代价
    // dp[i] = Math.min(dp[i-2]+cost[i-2], dp[i-1]+cost[i-1]);
    // 初始值：dp[0]=dp[1]=0
    // 返回值：dp[n]
    // 优化：只与前两项有关，声明两个变量轮动
    p, q, tmp := 0, 0 ,0 
    for i := 2; i <= n; i++ {
        tmp = q
        q = min(p + cost[i - 2], q + cost[i - 1])
        p = tmp
    }

    return q
}

func min(a, b int) int {
    if a > b {
        return b
    }

    return a
}